package jago02.jago0201.ag01_sort;

import java.util.Arrays;

/**
 * 插入排序
 * 杂化简：每一轮将无序数组的首位划分到有序数组末尾，再从后往前遍历有序数组，找到元素合适的位置
 * 解目录：
 *      0.将数组分为有序数组和无序数组，左边为有序数组，右边为无序数组
 *      1.初始化有序数组范围为0-0，无序数组i-n(i默认1，n为数组长度)
 *      2.将i划入有序数组，从后往前遍历有序数组，i位置元素依次和有序数组元素比较，如果小于则交换，直到找到i在有序数组中合适的位置
 *      3.i不再属于无序数组，无序数组长度起始位置限更新为i=i+1，继续下轮比较
 * 复杂度：O(N~2)
 */
public class Sort03_Insertion {
    public static void main(String[] args) {
        Comparable[] arr = new Comparable[]{1,5,2,3,4,6,8,0};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(Comparable[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j >0 ; j--) {
                if (bigThan(arr[j-1],arr[j])){
                    exch(arr,j-1,j);
                }else{
                    break;
                }
            }
        }
    }

    private static void exch(Comparable[] arr, int j, int i) {
        Comparable tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    private static boolean bigThan(Comparable m, Comparable n) {
       return m.compareTo(n)>0;
    }
}
